Kingman's formula

In queueing theory, Kingman's formula is an approximation for G/G/1 queues and states that the mean waiting time is given by

$\mathbb{E}(W_q) \approx \left( \frac{\rho}{1-\rho} \right) \left( \frac{c_a^2%2Bc_s^2}{2}\right) \tau$

Where $\tau$ is the mean service time (i.e. $\mu=1/\tau$ is the service rate), $\lambda$ is the mean arrival rate, $\rho=\lambda \tau = \lambda/\mu$ is the utilization, c_a is the coefficient of variation for arrivals (that is the standard deviation of arrival times divided by the mean arrival time) and c_s is the coefficient of variation for service times (standard deviation of service time divided by mean service time $\tau$ ).

The formula is the product of three terms, which depend on Utilization, Variability and Service time, respectively. This has a nice interpretation: it shows that the expected waiting time increases when service is slow, or when service and/or arrival times are highly variable or when the system is very busy (rho close to one).

It was first published by John Kingman in his 1966 paper "On the Algebra of Queues." It is known to be generally very accurate^[1] for a system that is operating close to saturation.

References

^ Harrison, Peter G.; Patel, Naresh M., Performance Modelling of Communication Networks and Computer Architectures, pp. 336, ISBN 0201544199